from typing import List

MAX_INT = 10**6


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        dp1 = arr[0]

        for i in range(1, n):
            # 统计前缀后缀最大值
            prefix = [MAX_INT] * (n + 1)
            suffix = [MAX_INT] * (n + 1)
            for j in range(n):
                prefix[j + 1] = min(prefix[j], dp1[j])
            for j in range(n - 1, -1, -1):
                suffix[j] = min(suffix[j + 1], dp1[j])

            # 状态转移
            dp2 = [0] * n
            for j in range(n):
                dp2[j] += min(prefix[j], suffix[j + 1]) + arr[i][j]
            dp1 = dp2

        return min(dp1)


if __name__ == "__main__":
    print(Solution().minFallingPathSum(arr=[[1, 2, 3],
                                            [4, 5, 6],
                                            [7, 8, 9]]))  # 13
